{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Performance of a Team"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxPerformance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大的团队表现值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个整数 <code>n</code> 和 <code>k</code>，以及两个长度为 <code>n</code> 的整数数组 <code>speed</code> 和<code> efficiency</code>。现有 <code>n</code> 名工程师，编号从 <code>1</code> 到 <code>n</code>。其中 <code>speed[i]</code>&nbsp;和 <code>efficiency[i]</code>&nbsp;分别代表第 <code>i</code>&nbsp;位工程师的速度和效率。</p>\n",
    "\n",
    "<p>从这 <code>n</code> 名工程师中最多选择 <code>k</code> 名不同的工程师，使其组成的团队具有最大的团队表现值。</p>\n",
    "\n",
    "<p><strong>团队表现值</strong>&nbsp;的定义为：一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。</p>\n",
    "\n",
    "<p>请你返回该团队的​​​​​​最大团队表现值，由于答案可能很大，请你返回结果对 <code>10^9 + 7</code> 取余后的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2\n",
    "<strong>输出：</strong>60\n",
    "<strong>解释：</strong>\n",
    "我们选择工程师 2（speed=10 且 efficiency=4）和工程师 5（speed=5 且 efficiency=7）。他们的团队表现值为 performance = (10 + 5) * min(4, 7) = 60 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3\n",
    "<strong>输出：</strong>68\n",
    "<strong>解释：\n",
    "</strong>此示例与第一个示例相同，除了 k = 3 。我们可以选择工程师 1 ，工程师 2 和工程师 5 得到最大的团队表现值。表现值为 performance = (2 + 10 + 5) * min(5, 4, 7) = 68 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4\n",
    "<strong>输出：</strong>72\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= n &lt;= 10^5</code></li>\n",
    "\t<li><code>speed.length == n</code></li>\n",
    "\t<li><code>efficiency.length == n</code></li>\n",
    "\t<li><code>1 &lt;= speed[i] &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= efficiency[i] &lt;= 10^8</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-performance-of-a-team](https://leetcode.cn/problems/maximum-performance-of-a-team/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-performance-of-a-team](https://leetcode.cn/problems/maximum-performance-of-a-team/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6\\n[2,10,3,1,5,8]\\n[5,4,3,9,7,2]\\n2', '6\\n[2,10,3,1,5,8]\\n[5,4,3,9,7,2]\\n3', '6\\n[2,10,3,1,5,8]\\n[5,4,3,9,7,2]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        dp, sm, res, heap = sorted(range(n), key = lambda x:efficiency[x], reverse = True), 0, 0, []\n",
    "        for i in range(k):\n",
    "            x = dp[i]\n",
    "            sm += speed[x]\n",
    "            heap.append(speed[x])\n",
    "            res = max(res, sm * efficiency[x])\n",
    "        heapq.heapify(heap)\n",
    "        for i in range(k,n):\n",
    "            s, e = speed[dp[i]], efficiency[dp[i]]\n",
    "            if s > heap[0]:\n",
    "                sm += s - heap[0]\n",
    "                heapq.heapreplace(heap, s)\n",
    "                res = max(res, sm * e)\n",
    "        return res % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, sp: List[int], ef: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        se = sorted(zip(ef, sp), reverse=True)\n",
    "        ans = 0\n",
    "        q = []\n",
    "        sm = 0\n",
    "        for e, s in se:\n",
    "            sm += s\n",
    "            heapq.heappush(q, s)\n",
    "            while len(q) > k:\n",
    "                sm -= heapq.heappop(q)\n",
    "            ans = max(ans, sm * e)\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        heap = []\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        for eff, sp in sorted(zip(efficiency, speed), reverse = True):\n",
    "            if len(heap) == k:\n",
    "                s -= heappop(heap)\n",
    "            heappush(heap, sp)\n",
    "            s += sp\n",
    "            ans = max(ans, eff * s)\n",
    "        return ans % MOD\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        spef = [(eff, spd) for eff, spd in zip(efficiency, speed)]\n",
    "        spef.sort(reverse=True)\n",
    "        q = []\n",
    "        ans = -inf\n",
    "        acc = 0\n",
    "        for eff, spd in spef:\n",
    "            if len(q) < k:\n",
    "                acc += spd\n",
    "                heapq.heappush(q, spd)\n",
    "                ans = max(ans, acc * eff)\n",
    "            elif len(q) >= k and spd <= q[0]:\n",
    "                continue\n",
    "            else:\n",
    "                heapq.heappush(q, spd)\n",
    "                acc = acc + spd - heapq.heappop(q)\n",
    "                ans = max(ans, acc * eff)\n",
    "        return ans % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        comb = sorted(zip(efficiency, speed), reverse=True)  # 按 efficiency 降序排序\n",
    "        shp = 0\n",
    "        hp = []\n",
    "        ans = 0\n",
    "        for e, s in comb:\n",
    "            if len(hp) == k:\n",
    "                if hp[0] < s:\n",
    "                    x = heappop(hp)\n",
    "                    heappush(hp, s)\n",
    "                    shp += (s - x)\n",
    "            else:\n",
    "                heappush(hp, s)\n",
    "                shp += s\n",
    "            ans = max(ans, shp * e)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        test = []\n",
    "        for i in range(n):\n",
    "            test.append((efficiency[i], speed[i]))\n",
    "        test.sort(reverse=True)\n",
    "        heaq = []\n",
    "        res = 0\n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            total += test[i][1]\n",
    "            heapq.heappush(heaq, test[i][1])\n",
    "            if len(heaq) > k:\n",
    "                total -= heapq.heappop(heaq)\n",
    "            res = max(res, total * test[i][0])\n",
    "        return res % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        \n",
    "        h = []\n",
    "        total = 0\n",
    "        ans = 0\n",
    "        for a, b in reversed(sorted(zip(efficiency, speed))):\n",
    "            heappush(h, b)\n",
    "            total += b\n",
    "            if len(h) > k:\n",
    "                t = heappop(h)\n",
    "                total -= t\n",
    "            ans = max(ans, total * a)\n",
    "        return int(ans % (10**9 + 7))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        mod = 1000000007\n",
    "        ans = 0\n",
    "        \n",
    "        h = []\n",
    "        score = 0\n",
    "\n",
    "        def move_up(i):\n",
    "            j = (i-1)//2\n",
    "            while j >= 0 and h[j] > h[i]:\n",
    "                h[i],h[j] = h[j],h[i]\n",
    "                i,j = j,(j-1)//2\n",
    "        \n",
    "        def move_down(i,lim):\n",
    "            j = i*2+1\n",
    "            while j < lim:\n",
    "                if j+1 < lim and h[j+1] < h[j]: j += 1\n",
    "                if h[j] < h[i]:\n",
    "                    h[i],h[j] = h[j],h[i]\n",
    "                    i,j = j, j*2+1\n",
    "                else: break\n",
    "            \n",
    "        def heap_push(x):\n",
    "            nonlocal score\n",
    "            h.append(x)\n",
    "            score += x\n",
    "            move_up(len(h)-1)\n",
    "            if len(h) > k:\n",
    "                h[0],h[-1] = h[-1],h[0]\n",
    "                move_down(0,len(h)-1)\n",
    "                score -= h.pop()\n",
    "\n",
    "        for e,s in sorted(zip(efficiency,speed),reverse=True):\n",
    "            heap_push(s)\n",
    "            ans = max(ans,score * e)\n",
    "\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        ans = sum_s = 0\n",
    "        pq = []\n",
    "        for i,(e,s) in enumerate(sorted(zip(efficiency,speed),reverse = True)):\n",
    "            sum_s += s\n",
    "            heappush(pq,s)\n",
    "            if len(pq) > k:\n",
    "                sum_s -= heappop(pq)\n",
    "            ans = max(ans,e*sum_s)\n",
    "\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        # 选子序列\n",
    "        MOD = 10**9 + 7\n",
    "        ans = sum_sp = 0\n",
    "        pq = [] # 维护前k - 1个最大speed\n",
    "        # 从高到低枚举最小效率，这样前面的元素的效率都更高，不影响后面的计算，速度和从前面元素里选最大的k - 1个即可，用堆来维护\n",
    "        for i,(e,s) in enumerate(sorted(zip(efficiency,speed),reverse = True)):\n",
    "            # sum_sp * e\n",
    "            ans = max(ans,(sum_sp + s) * e)\n",
    "            # 维护前k - 1个最大值\n",
    "            sum_sp += s\n",
    "            heappush(pq,s)\n",
    "            if len(pq) > k - 1:\n",
    "                sum_sp -= heappop(pq)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        e_list = list(zip(efficiency, speed))\n",
    "        e_list.sort(reverse=True)\n",
    "        heap = []\n",
    "        sum_speed = 0\n",
    "        max_res = 0\n",
    "        for e, s in e_list:\n",
    "            if len(heap) < k:\n",
    "                heapq.heappush(heap, s)\n",
    "                sum_speed += s\n",
    "\n",
    "            else:\n",
    "                out = heapq.heappushpop(heap, s)\n",
    "                sum_speed += s - out\n",
    "            res = e * sum_speed\n",
    "            max_res = max(max_res, res)\n",
    "        return max_res%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        engineers = sorted(zip(efficiency, speed), reverse=True)\n",
    "        # print(engineers)\n",
    "        ans, selected, s_sum = 0, [], 0\n",
    "        for e, s in engineers:\n",
    "            heappush(selected, s)\n",
    "            s_sum += s\n",
    "            ans = max(ans, s_sum * e)\n",
    "            if len(selected) == k:\n",
    "                s_remove = heappop(selected)\n",
    "                s_sum -= s_remove\n",
    "        return ans % (10**9 + 7) \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        efficiency=sorted([(efficiency[i],speed[i]) for i in range(n)],reverse=True)\n",
    "        pq,sumpq,ans=[],0,0\n",
    "        for i in range(0,n):\n",
    "            heapq.heappush(pq,(efficiency[i][1]));\n",
    "            sumpq+=efficiency[i][1]\n",
    "            while(len(pq)>k):sumpq-=pq[0];heapq.heappop(pq)\n",
    "            ans=max(ans,sumpq*efficiency[i][0])\n",
    "        return ans%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        MOD=10**9+7\n",
    "        if k==1:\n",
    "            return max([(efficiency[i]*speed[i])%MOD for i in range(n)])\n",
    "        Person=[(efficiency[i],speed[i])for i in range(n)]\n",
    "        #效率大的排前面,按照效率递减排序\n",
    "        Person=sorted(Person)[::-1]\n",
    "        mini_heap=[]\n",
    "        res=0\n",
    "        cur_sum=0\n",
    "        for i in range(n):\n",
    "            eff,spd=Person[i]\n",
    "            #堆还没有满,新元素直接加入\n",
    "            if i<k:\n",
    "                heapq.heappush(mini_heap,spd)\n",
    "                cur_sum+=spd\n",
    "            #堆已经满了\n",
    "            else:\n",
    "                #堆顶(最小的速度)小于当前person的速度\n",
    "                if mini_heap[0]<spd:\n",
    "                    cur_sum=cur_sum-mini_heap[0]+spd\n",
    "                    heapq.heappop(mini_heap)\n",
    "                    heapq.heappush(mini_heap,spd)\n",
    "            res=max(res,cur_sum*eff)\n",
    "        return res%MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        if k == 1:\n",
    "            return max([efficiency[i] * speed[i] % MOD for i in range(n)])\n",
    "        Person = [(efficiency[i],speed[i])for i in range(n)]\n",
    "        Person = sorted(Person)[::-1]\n",
    "        stack = []\n",
    "        res = 0\n",
    "        cur_sum = 0\n",
    "        for i in range(n):\n",
    "            e,s = Person[i]\n",
    "            #堆还没满\n",
    "            if i < k:\n",
    "                heapq.heappush(stack,s)\n",
    "                cur_sum += s\n",
    "            else:\n",
    "                #堆顶(最小的速度)小于当前person的速度\n",
    "                if stack[0] < s:\n",
    "                    cur_sum = cur_sum - stack[0] + s\n",
    "                    heapq.heappop(stack)\n",
    "                    heapq.heappush(stack,s)\n",
    "            res = max(res,cur_sum * e)\n",
    "        return res % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        index=sorted(range(n),key=lambda x:-efficiency[x])\n",
    "        ans,pq,total=0,[],0\n",
    "        for i in range(n):\n",
    "            total+=speed[index[i]]\n",
    "            heappush(pq,speed[index[i]])\n",
    "            if len(pq)>k:\n",
    "                tmp=heappop(pq)\n",
    "                total-=tmp\n",
    "            ans=max(ans,total*efficiency[index[i]])\n",
    "        return ans%(10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        speed_eff = zip(speed,efficiency)\n",
    "        speed_eff = sorted(speed_eff,key=lambda x:x[1],reverse=True)\n",
    "        total = 0\n",
    "        res = 0\n",
    "        stack = []\n",
    "        for sp,ef in speed_eff:\n",
    "            total += sp\n",
    "            res = max(res,total*ef)\n",
    "            heapq.heappush(stack,sp)\n",
    "            if len(stack) == k:\n",
    "                total -= heapq.heappop(stack)\n",
    "        return res % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        sorted_lists = sorted(zip(speed, efficiency), key=lambda x: x[1])\n",
    "        heap = []\n",
    "        sum_heap = 0\n",
    "        res = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if i + k > n - 1:\n",
    "                heapq.heappush(heap, sorted_lists[i][0])\n",
    "                sum_heap += sorted_lists[i][0]\n",
    "                res = max(res, sum_heap * sorted_lists[i][1])\n",
    "            else:\n",
    "                if sorted_lists[i][0] > heap[0]:\n",
    "                    sum_heap = sum_heap - heap[0] + sorted_lists[i][0]\n",
    "                    heapq.heappop(heap)\n",
    "                    heapq.heappush(heap, sorted_lists[i][0])\n",
    "                    res = max(res, sum_heap * sorted_lists[i][1])\n",
    "        return res % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        ps=sorted(zip(efficiency,speed),key=lambda t:t[0],reverse=True)\n",
    "        pq=[];s=0\n",
    "        res=0\n",
    "        for ef,sp in ps:\n",
    "            res=max(res,ef*(s+sp))\n",
    "            if k==1: continue\n",
    "            elif len(pq)<k-1:\n",
    "                heappush(pq,sp)\n",
    "                s+=sp\n",
    "            elif len(pq)==k-1 and pq[0]<sp:\n",
    "                s+=sp-heappop(pq)\n",
    "                heappush(pq,sp)\n",
    "        return res%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        index=sorted(range(n),key=lambda x:-efficiency[x])\n",
    "        ans,pq,total=0,[],0\n",
    "        for i in range(n):\n",
    "            total+=speed[index[i]]\n",
    "            heappush(pq,speed[index[i]])\n",
    "            if len(pq)>k:\n",
    "                tmp=heappop(pq)\n",
    "                total-=tmp\n",
    "            ans=max(ans,total*efficiency[index[i]])\n",
    "        return ans%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        # 固定efficiency，枚举最小的min_eff，用最小堆求出\n",
    "        # eff大于min_eff的最大的k-1个数。\n",
    "        # 按照eff降序排序，那么遍历过程中，在之前的所有工程师的eff都是大于当前eff的\n",
    "        # 注意，并不一定要选k个，可以少于k个工程师\n",
    "        MOD = 10**9+7\n",
    "        max_res = 0\n",
    "        rec = [(efficiency[i], speed[i]) for i in range(n)]\n",
    "        rec.sort(key=lambda x:x[0], reverse=True)\n",
    "        mheap = []\n",
    "        cur_sum = 0\n",
    "        for i in range(n):\n",
    "            min_eff, cur_s = rec[i][0], rec[i][1]\n",
    "            max_res = max(max_res, (cur_sum+cur_s)*min_eff)\n",
    "            if k>1:\n",
    "                if len(mheap)<k-1:\n",
    "                    heapq.heappush(mheap, cur_s)\n",
    "                    cur_sum += cur_s\n",
    "                else:\n",
    "                    if cur_s>mheap[0]:\n",
    "                        cur_sum += (cur_s - mheap[0])\n",
    "                        heapq.heappop(mheap)\n",
    "                        heapq.heappush(mheap, cur_s)\n",
    "\n",
    "        return max_res%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        index=sorted(range(n),key=lambda x:-efficiency[x])\n",
    "        ans,pq,total=0,[],0\n",
    "        for i in range(n):\n",
    "            total+=speed[index[i]]\n",
    "            heappush(pq,speed[index[i]])\n",
    "            if len(pq)>k:\n",
    "                tmp=heappop(pq)\n",
    "                total-=tmp\n",
    "            ans=max(ans,total*efficiency[index[i]])\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        index=sorted(range(n),key=lambda x:-efficiency[x])\n",
    "        ans,pq,total=0,[],0\n",
    "        for i in range(n):\n",
    "            total+=speed[index[i]]\n",
    "            heappush(pq,speed[index[i]])\n",
    "            if len(pq)>k:\n",
    "                tmp=heappop(pq)\n",
    "                total-=tmp\n",
    "            ans=max(ans,total*efficiency[index[i]])\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        # 固定efficiency，枚举最小的min_eff，用最小堆求出\n",
    "        # eff大于min_eff的最大的k-1个数。\n",
    "        # 按照eff降序排序，那么遍历过程中，在之前的所有工程师的eff都是大于当前eff的\n",
    "        MOD = 10**9+7\n",
    "        max_res = 0\n",
    "        rec = [(efficiency[i], speed[i]) for i in range(n)]\n",
    "        rec.sort(key=lambda x:x[0], reverse=True)\n",
    "        mheap = []\n",
    "        cur_sum = 0\n",
    "        for i in range(n):\n",
    "            min_eff, cur_s = rec[i][0], rec[i][1]\n",
    "            max_res = max(max_res, (cur_sum+cur_s)*min_eff)\n",
    "            if k>1:\n",
    "                if len(mheap)<k-1:\n",
    "                    heapq.heappush(mheap, cur_s)\n",
    "                    cur_sum += cur_s\n",
    "                else:\n",
    "                    if cur_s>mheap[0]:\n",
    "                        cur_sum += (cur_s - mheap[0])\n",
    "                        heapq.heappop(mheap)\n",
    "                        heapq.heappush(mheap, cur_s)\n",
    "\n",
    "        return max_res%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        items = [(speed[i], efficiency[i]) for i in range(n)]\n",
    "        items.sort(key = lambda item: item[1], reverse = True)\n",
    "        total = 0\n",
    "        ans = 0\n",
    "\n",
    "        pq = PriorityQueue()\n",
    "\n",
    "        for i in range(n):\n",
    "            pq.put(items[i][0])\n",
    "            total += items[i][0]\n",
    "            if pq.qsize()>k:\n",
    "                total -= pq.get()\n",
    "\n",
    "            ans = max(ans,total*items[i][1])\n",
    "\n",
    "        return ans %(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        items = [(speed[i], efficiency[i]) for i in range(n)]\n",
    "        items.sort(key = lambda item: item[1], reverse = True)\n",
    "        total = 0\n",
    "        ans = 0\n",
    "\n",
    "        pq = PriorityQueue()\n",
    "\n",
    "        for i in range(n):\n",
    "            pq.put(items[i][0])\n",
    "            total += items[i][0]\n",
    "            if pq.qsize()>k:\n",
    "                total -= pq.get()\n",
    "\n",
    "            ans = max(ans,total*items[i][1])\n",
    "\n",
    "        return ans %(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        # 固定efficiency，枚举最小的min_eff，用最小堆求出\n",
    "        # eff大于min_eff的最大的k-1个数。\n",
    "        # 按照eff降序排序，那么遍历过程中，在之前的所有数都是eff大于\n",
    "        # 当前eff的数\n",
    "        MOD = 10**9+7\n",
    "        max_res = 0\n",
    "        rec = [(efficiency[i], speed[i]) for i in range(n)]\n",
    "        rec.sort(key=lambda x:x[0], reverse=True)\n",
    "        mheap = []\n",
    "        cur_sum = 0\n",
    "        for i in range(n):\n",
    "            min_eff, cur_s = rec[i][0], rec[i][1]\n",
    "            max_res = max(max_res, (cur_sum+cur_s)*min_eff)\n",
    "            if k>1:\n",
    "                if len(mheap)<k-1:\n",
    "                    heapq.heappush(mheap, cur_s)\n",
    "                    cur_sum += cur_s\n",
    "                else:\n",
    "                    if cur_s>mheap[0]:\n",
    "                        cur_sum += (cur_s - mheap[0])\n",
    "                        heapq.heappop(mheap)\n",
    "                        heapq.heappush(mheap, cur_s)\n",
    "        return max_res%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        import heapq\n",
    "        lst = [[efficiency[i], speed[i]] for i in range(n)]\n",
    "        lst.sort(reverse=True)\n",
    "        heap = []\n",
    "        Sum = 0\n",
    "        Max = 0\n",
    "        for i in range(k):\n",
    "            heapq.heappush(heap, lst[i][1])\n",
    "            Sum += lst[i][1]\n",
    "            Max = max(Max, Sum * lst[i][0])\n",
    "\n",
    "        for i in range(k, n):\n",
    "            sp = heapq.heappushpop(heap, lst[i][1])\n",
    "            Sum += (lst[i][1] - sp)\n",
    "            Max = max(Max, Sum * lst[i][0])\n",
    "\n",
    "        return Max % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        ability = [[efficiency[i], speed[i]] for i in range(n)]\n",
    "        ability.sort()\n",
    "        #print(ability)\n",
    "        res = 0\n",
    "        speed, efficiency = 0, 0\n",
    "        idx = []#按speed排序\n",
    "        mode = 10 **9 + 7\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if len(idx) < k:\n",
    "                efficiency = ability[i][0]\n",
    "                speed += ability[i][1]\n",
    "                heapq.heappush(idx, ability[i][1])\n",
    "                res = max(res, efficiency * speed)\n",
    "            else:\n",
    "                efficiency = ability[i][0]\n",
    "                heapq.heappush(idx, ability[i][1])\n",
    "                speed = speed + ability[i][1] - heapq.heappop(idx)\n",
    "                res = max(res, efficiency * speed)\n",
    "            #print(efficiency, speed, res, idx)\n",
    "        return res % mode\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        ans = 0\n",
    "        ss = sorted([[e, s] for s, e in zip(speed, efficiency)], reverse=True)\n",
    "        h, sm = [], 0\n",
    "        for e, s in ss:\n",
    "            heappush(h, s)\n",
    "            sm += s\n",
    "            if len(h) > k:\n",
    "                sm -= heappop(h)\n",
    "            ans = max(ans, e * sm)\n",
    "        return ans % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        spef = [(eff, spd) for eff, spd in zip(efficiency, speed)]\n",
    "        spef.sort(reverse=True)\n",
    "        print(spef)\n",
    "        sl = SortedList()\n",
    "        ans = -inf\n",
    "        acc = 0\n",
    "        for eff, spd in spef:\n",
    "            if len(sl) < k:\n",
    "                acc += spd\n",
    "                sl.add(spd)\n",
    "                ans = max(ans, acc * eff)\n",
    "            elif len(sl) >= k and spd <= sl[0]:\n",
    "                continue\n",
    "            else:\n",
    "                sl.add(spd)\n",
    "                acc = acc + spd - sl.pop(0)\n",
    "                ans = max(ans, acc * eff)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        #2542. 最大子序列的分数\n",
    "        nums = sorted(zip(speed,efficiency),key=lambda x:-x[1])#小根堆，-x[1]降序排序\n",
    "        h = []\n",
    "        s = 0\n",
    "        res = 0 \n",
    "        for a,b in nums:\n",
    "            if len(h)>=k:#最多选择K个\n",
    "                s -= heapq.heappop(h)\n",
    "            heapq.heappush(h,a)\n",
    "            s += a\n",
    "            res = max(res,s*b)\n",
    "        return res%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        pers=[(speed[i],efficiency[i]) for i in range(n)]\n",
    "        pers.sort(key=lambda per:-per[1])\n",
    "        h=[]\n",
    "        speed_sum=0\n",
    "        ans=0\n",
    "        b=10**9+7\n",
    "        for i in range(n):\n",
    "            speed,ef=pers[i]\n",
    "            speed_sum+=speed\n",
    "            heappush(h,speed)\n",
    "            if len(h)>k:\n",
    "                speed_sum-=heappop(h)\n",
    "            ans=max(ans,speed_sum*ef)\n",
    "        return ans%b\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        n = len(speed)\n",
    "        staff = []\n",
    "        for i in range(n):\n",
    "            staff.append((speed[i], efficiency[i]))\n",
    "        pq = []\n",
    "        staff.sort(key = lambda x: -x[1])\n",
    "        ans = pre_sum = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            vol, eff = staff[i]\n",
    "            if len(pq) < k:\n",
    "                heappush(pq, vol)\n",
    "                pre_sum += vol\n",
    "            elif len(pq) == k and pq[0] < vol:\n",
    "                pre_sum = pre_sum - pq[0] + vol\n",
    "                heappop(pq)\n",
    "                heappush(pq, vol)\n",
    "            ans = max(ans, pre_sum * eff)\n",
    "            \n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        nums = [(n1, n2) for n1, n2 in zip(speed, efficiency)]\n",
    "        nums.sort(key=lambda x: -x[1])\n",
    "        num_sum = 0\n",
    "        heap = []\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for sp, eff in nums:\n",
    "            if len(heap) == k:\n",
    "                num_sum -= heapq.heappop(heap)\n",
    "            \n",
    "            heapq.heappush(heap, sp)\n",
    "            num_sum += sp\n",
    "            ans = max(ans, num_sum * eff)\n",
    "\n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        h = []\n",
    "        sum = 0\n",
    "        ans = -inf\n",
    "        MOD = 10 ** 9 + 7\n",
    "        for s, e in sorted(zip(speed, efficiency), key=lambda x: -x[1]):\n",
    "            sum += s\n",
    "            heappush(h, s)\n",
    "            ans = max(ans, sum * e)\n",
    "            if len(h) > k - 1:\n",
    "                sum -= heappop(h)\n",
    "        return ans % MOD\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        import heapq\n",
    "        q = []\n",
    "        es = [(x,y) for x,y in zip(efficiency,speed)]\n",
    "        es.sort(key=lambda x:-x[0])\n",
    "        res = 0\n",
    "        total_s = 0\n",
    "        for e,s in es:\n",
    "            heapq.heappush(q,s)\n",
    "            total_s += s\n",
    "            while len(q) > k:\n",
    "                total_s -= heapq.heappop(q)\n",
    "            res = max(res,e*total_s)\n",
    "        return res%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        nums = [(s, e) for s, e in zip(speed, efficiency)]\n",
    "        nums.sort(key=lambda x : -x[1])\n",
    "        ans = 0\n",
    "        h = []\n",
    "        total = 0\n",
    "        for s, e in nums:\n",
    "            heappush(h, s)\n",
    "            total += s\n",
    "            if len(h) > k:\n",
    "                total -= heappop(h)\n",
    "            ans = max(ans, total * e)\n",
    "        return int(ans % MOD)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        nums = [(n1, n2) for n1, n2 in zip(speed, efficiency)]\n",
    "        nums.sort(key=lambda x: -x[1])\n",
    "        num_sum = 0\n",
    "        heap = []\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for sp, eff in nums:\n",
    "            if len(heap) == k:\n",
    "                num_sum -= heapq.heappop(heap)\n",
    "            \n",
    "            heapq.heappush(heap, sp)\n",
    "            num_sum += sp\n",
    "            ans = max(ans, num_sum * eff)\n",
    "\n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        minHeap = []    # min-heap, element: speed\n",
    "        speedSum = 0\n",
    "        # 1. O(NlogN) sort tuple arrays (speed[i], efficiency[i]) by efficiency[i] descendingly\n",
    "        tuples = sorted(zip(speed, efficiency), key=lambda x: -x[1])\n",
    "\n",
    "        # 2. O(nlogk) iterate over sorted tuple arrays\n",
    "        for s, e in tuples:\n",
    "            heappush(minHeap, s)\n",
    "            if len(minHeap) > k:\n",
    "                speedSum -= heappop(minHeap)\n",
    "            speedSum += s \n",
    "            ans = max(ans, speedSum * e)\n",
    "        \n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        h = []\n",
    "        ans = 0\n",
    "        pre = 0\n",
    "        MOD = 10**9 + 7\n",
    "        for s, e in sorted(zip(speed, efficiency), key=lambda x: -x[1]):\n",
    "            if len(h) == k:\n",
    "                pre -= heappop(h)\n",
    "            pre += s\n",
    "            heappush(h, s)\n",
    "            ans = max(ans, pre * e)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        pers=[(speed[i],efficiency[i]) for i in range(n)]\n",
    "        pers.sort(key=lambda per:-per[1])\n",
    "        h,speed_sum,ans=[],0,0\n",
    "        for i in range(n):\n",
    "            speed,ef=pers[i]\n",
    "            speed_sum+=speed\n",
    "            heappush(h,speed)\n",
    "            if len(h)>k:\n",
    "                speed_sum-=heappop(h)\n",
    "            ans=max(ans,speed_sum*ef)\n",
    "        return ans%(10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        pq = PriorityQueue()\n",
    "        \n",
    "        ans = 0\n",
    "        sum = 0\n",
    "        for e,s in sorted(zip(efficiency, speed), key=lambda x : -x[0]):\n",
    "            sum += s\n",
    "            ans = max(ans, sum * e)\n",
    "            pq.put(s)\n",
    "            if pq.qsize() == k:\n",
    "                sum -= pq.get()\n",
    "        return ans % int(1e9+7)\n",
    "        \n",
    "\n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:  # 2.\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "\n",
    "        max_performance, sum_speed = 0, 0\n",
    "        heap = []\n",
    "        sorted_people = sorted(zip(speed, efficiency), key=lambda x: -x[1])\n",
    "\n",
    "        for i, (s, e) in enumerate(sorted_people):\n",
    "            if i < k:\n",
    "                heapq.heappush(heap, s)\n",
    "                sum_speed += s\n",
    "            elif s > heap[0]:\n",
    "                sum_speed += s - heapq.heappushpop(heap, s)\n",
    "            max_performance = max(max_performance, sum_speed * e)\n",
    "\n",
    "        return max_performance % (1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:  # 2.\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "\n",
    "        max_performance, sum_speed = 0, 0\n",
    "        heap = []\n",
    "        sorted_people = sorted(zip(speed, efficiency), key=lambda x: -x[1])\n",
    "\n",
    "        for i, (s, e) in enumerate(sorted_people):\n",
    "            if i < k:\n",
    "                heapq.heappush(heap, s)\n",
    "                sum_speed += s\n",
    "            elif s > heap[0]:\n",
    "                sum_speed += s - heapq.heappushpop(heap, s)\n",
    "            max_performance = max(max_performance, sum_speed * e)\n",
    "\n",
    "        return max_performance % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        cur_s = ans = cnt = 0\n",
    "        heap = []\n",
    "        for s, e in sorted(zip(speed, efficiency), key=lambda x: -x[1]):\n",
    "            cur_s += s\n",
    "            cnt += 1\n",
    "            heappush(heap, s)\n",
    "            if cnt > k:\n",
    "                cur_s -= heappop(heap)\n",
    "                cnt -= 1\n",
    "            ans = max(ans, cur_s * e)\n",
    "        return ans % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        q = []\n",
    "        n = len(speed)\n",
    "        a = sorted(zip(speed, efficiency), key=lambda x: -x[1])\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            s += a[i][0]\n",
    "            heapq.heappush(q, a[i][0])\n",
    "            ans = max(ans, a[i][1] * s)\n",
    "        for i in range(k, n):\n",
    "            if a[i][0] > q[0]:\n",
    "                s -= heapq.heappop(q)\n",
    "                s += a[i][0]\n",
    "                heapq.heappush(q, a[i][0])\n",
    "                ans = max(ans, s * a[i][1])\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        \n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        total = list(zip(speed, efficiency))\n",
    "        total = sorted(total, key = lambda x: - x[1])\n",
    "        ans = 0\n",
    "        min_eff = total[0][1]\n",
    "        heap = []\n",
    "        lh = 0\n",
    "        max_sum = 0\n",
    "        for i, (x, y) in enumerate(total):\n",
    "            #print(x, y)\n",
    "            if y < min_eff:\n",
    "                min_eff = y\n",
    "            if lh < k:\n",
    "                heapq.heappush(heap, x)\n",
    "                max_sum += x\n",
    "                lh += 1\n",
    "            else:\n",
    "                max_sum += x\n",
    "                heapq.heappush(heap, x)\n",
    "                m = heapq.heappop(heap)\n",
    "                max_sum -= m\n",
    "            #print(heap, min_eff, max_sum)\n",
    "            ans = max(ans, min_eff * max_sum)\n",
    "        return ans % (10 ** 9 + 7)\n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        arr = sorted(list(zip(speed, efficiency)), key=lambda x: -x[1])\n",
    "        heap = []\n",
    "        sumnum = 0\n",
    "        res = 0\n",
    "        for speed, efficiency in arr:\n",
    "            if len(heap) < k:\n",
    "                heappush(heap, speed)\n",
    "                sumnum += speed\n",
    "            elif heap[0] < speed:\n",
    "                sumnum += speed - heappop(heap)\n",
    "                heappush(heap, speed)\n",
    "            res = max(res, sumnum*efficiency)\n",
    "        return res % (10**9 +7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        men = [(speed[i], efficiency[i]) for i in range(n)]\n",
    "        men = sorted(men, key=lambda x: -x[1])\n",
    "        ans, q, sum_speed = 0, [], 0\n",
    "        for man in men:\n",
    "            if len(q) == k:\n",
    "                mine = q[0]\n",
    "                if man[0] > mine:\n",
    "                    heapq.heappop(q)\n",
    "                    heapq.heappush(q, man[0])\n",
    "                    sum_speed += man[0] - mine\n",
    "                    ans = max(ans, sum_speed * man[1])\n",
    "            else:\n",
    "                heapq.heappush(q, man[0])\n",
    "                sum_speed += man[0]\n",
    "                ans = max(ans, sum_speed * man[1])\n",
    "        \n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        # speed之和乘以eff最小值\n",
    "\n",
    "        # 按effciency降序排序\n",
    "        eff_spd = [[eff, spd] for eff, spd in zip(efficiency, speed)] \n",
    "        eff_spd.sort(key=lambda x:-x[0])\n",
    "\n",
    "        # 维护一个speed有序\n",
    "        # 方便处理speed之和\n",
    "        spd_heap = [] \n",
    "        max_prod, sum_spd_heap = 0, 0\n",
    "        for i in range(n):\n",
    "            # 拿出当前eff\n",
    "            # 越早拿的eff越高\n",
    "            e_min = eff_spd[i][0]\n",
    "            # \n",
    "            if len(spd_heap) == k: \n",
    "                sum_spd_heap -= heapq.heappop(spd_heap)\n",
    "            heapq.heappush(spd_heap, eff_spd[i][1])\n",
    "            sum_spd_heap += eff_spd[i][1]\n",
    "            max_prod = max(max_prod, sum_spd_heap*e_min)\n",
    "        return max_prod % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        data=[[speed[i],efficiency[i]] for i in range(n)]\n",
    "        data.sort(key=lambda x:-x[1])\n",
    "        ans = 0\n",
    "        s = 0\n",
    "        for i in range(k):\n",
    "            s += data[i][0]\n",
    "            ans = max(ans,s*data[i][1])\n",
    "\n",
    "\n",
    "        q = queue.PriorityQueue()\n",
    "        s = 0\n",
    "        for i in range(k):\n",
    "            q.put(data[i][0])\n",
    "            s += data[i][0]\n",
    "\n",
    "        #ans = s*data[k-1][1]\n",
    "        for i in range(k,n):\n",
    "            val = q.get()\n",
    "            q.put(data[i][0])\n",
    "            s += data[i][0]-val\n",
    "            ans = max(ans,s*data[i][1])\n",
    "        return ans%mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: [int], efficiency: [int], k: int) -> int:\n",
    "        efficiency, speed = zip(*sorted(zip(efficiency, speed), key=lambda p: -p[0]))\n",
    "#        print(efficiency)\n",
    "#        print(speed)\n",
    "\n",
    "        sumspeed=0\n",
    "        h1=list()\n",
    "        maxed=0\n",
    "        for p in range(n):\n",
    "            mineff=efficiency[p]\n",
    "            if len(h1)>=k:\n",
    "                tmp=heapq.heappop(h1)\n",
    "                sumspeed-=tmp[0]\n",
    "            heapq.heappush(h1,[speed[p],efficiency[p]])\n",
    "            sumspeed+=speed[p]\n",
    "            maxed=max(maxed,mineff*sumspeed)\n",
    "#            print(h1,\"max\",maxed,\"sum speed:\",sumspeed,\" min eff:\", mineff)\n",
    "\n",
    "        return maxed%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: [int], efficiency: [int], k: int) -> int:\n",
    "        efficiency, speed = zip(*sorted(zip(efficiency, speed), key=lambda p: -p[0]))\n",
    "#        print(efficiency)\n",
    "#        print(speed)\n",
    "\n",
    "        sumspeed=0\n",
    "        h1=list()\n",
    "        maxed=0\n",
    "        for p in range(n):\n",
    "            mineff=efficiency[p]\n",
    "            if len(h1)>=k:\n",
    "                tmp=heapq.heappop(h1)\n",
    "                sumspeed-=tmp[0]\n",
    "            heapq.heappush(h1,[speed[p],efficiency[p]])\n",
    "            sumspeed+=speed[p]\n",
    "            maxed=max(maxed,mineff*sumspeed)\n",
    "#            print(h1,\"max\",maxed,\"sum speed:\",sumspeed,\" min eff:\", mineff)\n",
    "\n",
    "        return maxed%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        egine = []\n",
    "        enum = len(speed)\n",
    "        for i in range(enum):\n",
    "            egine.append((speed[i], efficiency[i]))\n",
    "        egine.sort(key=lambda x:(-x[1], x[0]))\n",
    "        minque = PriorityQueue()\n",
    "        ans = 0\n",
    "        modnum = 10**9+7\n",
    "        sumnum = 0\n",
    "        for sp, ef in egine:\n",
    "            while minque.qsize() > k - 1:\n",
    "                minsp, minef = minque.get()\n",
    "                sumnum -= minsp\n",
    "            sumnum += sp\n",
    "            minque.put((sp, ef))\n",
    "            ans = max(ans, sumnum*ef)\n",
    "        return ans % modnum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        g=collections.defaultdict(list)\n",
    "        for s,e in zip(speed,efficiency):\n",
    "            g[e].append(s) \n",
    "        ks=list(g.keys())\n",
    "        ks.sort(reverse=True)\n",
    "        q=[]\n",
    "        ans=t=0\n",
    "        for ke in ks:\n",
    "\n",
    "            for v in g[ke]:\n",
    "                \n",
    "                heapq.heappush(q, v)\n",
    "               # print('q',q)\n",
    "                t+=v\n",
    "                if len(q)>k:\n",
    "                   # print('in')\n",
    "                    t-=heapq.heappop(q)\n",
    "         #   print(ke,t,ke*t)\n",
    "            ans=max(ans,ke*t)\n",
    "        return ans%(10**9+7)\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue, Queue\n",
    "class person:\n",
    "    def __init__(self, speed: int, efficiency: int):\n",
    "        self.speed = speed\n",
    "        self.efficiency = efficiency\n",
    "    def __lt__(self, other):\n",
    "        return self.speed < other.speed\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        personlist = []\n",
    "        personlen = len(speed)\n",
    "        for idx in range(personlen):\n",
    "            personlist.append(person(speed[idx], efficiency[idx]))\n",
    "        personlist = sorted(personlist, key=lambda x:x.efficiency, reverse=True)\n",
    "        res = 0\n",
    "        quesum = 0\n",
    "        bigque = PriorityQueue()\n",
    "        for item in personlist:\n",
    "            res = max(res, (item.speed+quesum) * item.efficiency)\n",
    "            bigque.put(item)\n",
    "            quesum += item.speed\n",
    "            while bigque.qsize() > k-1:\n",
    "                now = bigque.get()\n",
    "                quesum -= now.speed\n",
    "        return res % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class Staff:\n",
    "        def __init__(self, s, e):\n",
    "            self.s = s\n",
    "            self.e = e\n",
    "        \n",
    "        def __lt__(self, that):\n",
    "            return self.s < that.s \n",
    "    \n",
    "    \n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        v = list()\n",
    "        for i in range(n):\n",
    "            v.append(Solution.Staff(speed[i], efficiency[i]))\n",
    "        v.sort(key = lambda x: -x.e)\n",
    "\n",
    "        q = list()\n",
    "\n",
    "        ans = 0\n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            minE, totalS = v[i].e, total + v[i].s\n",
    "            ans = max(ans, minE * totalS)\n",
    "            heapq.heappush(q, v[i])\n",
    "            total += v[i].s\n",
    "            if len(q) == k:\n",
    "                item = heapq.heappop(q)\n",
    "                total -= item.s\n",
    "        return ans % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class Staff:\n",
    "        def __init__(self, s, e):\n",
    "            self.s = s \n",
    "            self.e = e \n",
    "        \n",
    "        def __lt__(self, that):\n",
    "            return self.s < that.s\n",
    "\n",
    "\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        v = list()\n",
    "        for i in range(n):\n",
    "            v.append(Solution.Staff(speed[i], efficiency[i]))\n",
    "        \n",
    "        v.sort(key = lambda x: -x.e)\n",
    "\n",
    "        q = list()\n",
    "        if n < k:\n",
    "            return sum(speed)*min(efficiency) % (10**9 + 7)\n",
    "            \n",
    "        ans, total = 0, 0\n",
    "        for i in range(n):\n",
    "            min_e = v[i].e\n",
    "            total_s = total + v[i].s\n",
    "\n",
    "            ans = max(ans, total_s*min_e)\n",
    "            heapq.heappush(q, v[i])\n",
    "            total += v[i].s\n",
    "            if len(q) == k:\n",
    "                item = heapq.heappop(q)\n",
    "                total -= item.s\n",
    "        \n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        ppl = list(zip(efficiency, speed))\n",
    "        ppl.sort(key = lambda x : (-x[0], -x[1]))\n",
    "\n",
    "        pq = []\n",
    "        heapq.heapify(pq)\n",
    "        res = 0\n",
    "        sum_max_speed = 0 # sum of the current max speed under constraint <= k\n",
    "        MOD = 10**9 + 7\n",
    "        for i in range(k):\n",
    "            heapq.heappush(pq, ppl[i][1])\n",
    "            sum_max_speed = (sum_max_speed + ppl[i][1])\n",
    "            curr_perf = ppl[i][0] * (sum_max_speed)\n",
    "            res = max(res, curr_perf)\n",
    "\n",
    "        for i in range(k, n):\n",
    "            min_speed = heapq.heappop(pq)\n",
    "            sum_max_speed = (sum_max_speed - min_speed)\n",
    "            heapq.heappush(pq, ppl[i][1])\n",
    "            sum_max_speed = (sum_max_speed + ppl[i][1])\n",
    "            curr_perf = ppl[i][0] * (sum_max_speed)\n",
    "            res = max(res, curr_perf)\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    class Staff:\n",
    "        def __init__(self, s, e):\n",
    "            self.s = s\n",
    "            self.e = e\n",
    "        \n",
    "        def __lt__(self, that):\n",
    "            return self.s < that.s\n",
    "        \n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        v = list()\n",
    "        for i in range(n):\n",
    "            v.append(Solution.Staff(speed[i], efficiency[i]))\n",
    "        v.sort(key=lambda x: -x.e)\n",
    "\n",
    "        q = list()\n",
    "        ans, total = 0, 0\n",
    "        for i in range(n):\n",
    "            minE, totalS = v[i].e, total + v[i].s\n",
    "            ans = max(ans, minE * totalS)\n",
    "            heapq.heappush(q, v[i])\n",
    "            total += v[i].s\n",
    "            if len(q) == k:\n",
    "                item = heapq.heappop(q)\n",
    "                total -= item.s\n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class Staff:\n",
    "        def __init__(self, s, e):\n",
    "            self.s = s\n",
    "            self.e = e\n",
    "        \n",
    "        def __lt__(self, that):\n",
    "            return self.s < that.s\n",
    "        \n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        v = list()\n",
    "        for i in range(n):\n",
    "            v.append(Solution.Staff(speed[i], efficiency[i]))\n",
    "        v.sort(key=lambda x: -x.e)\n",
    "\n",
    "        q = list()\n",
    "        ans, total = 0, 0\n",
    "        for i in range(n):\n",
    "            minE, totalS = v[i].e, total + v[i].s\n",
    "            ans = max(ans, minE * totalS)\n",
    "            heapq.heappush(q, v[i])\n",
    "            total += v[i].s\n",
    "            if len(q) == k:\n",
    "                item = heapq.heappop(q)\n",
    "                total -= item.s\n",
    "        return ans % (10**9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class Staff:\n",
    "        def __init__(self, s, e):\n",
    "            self.s = s \n",
    "            self.e = e \n",
    "        \n",
    "        def __lt__(self, that):\n",
    "            return self.s < that.s\n",
    "\n",
    "\n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        v = list()\n",
    "        for i in range(n):\n",
    "            v.append(Solution.Staff(speed[i], efficiency[i]))\n",
    "        \n",
    "        v.sort(key = lambda x: -x.e)\n",
    "\n",
    "        q = list()\n",
    "        if n < k:\n",
    "            return sum(speed)*min(efficiency) % (10**9 + 7)\n",
    "            \n",
    "        ans, total = 0, 0\n",
    "        for i in range(n):\n",
    "            min_e = v[i].e\n",
    "            total_s = total + v[i].s\n",
    "\n",
    "            ans = max(ans, total_s*min_e)\n",
    "            heapq.heappush(q, v[i])\n",
    "            total += v[i].s\n",
    "            if len(q) == k:\n",
    "                item = heapq.heappop(q)\n",
    "                total -= item.s\n",
    "        \n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class Staff:\n",
    "        def __init__(self, s, e):\n",
    "            self.s = s\n",
    "            self.e = e\n",
    "        \n",
    "        def __lt__(self, that):\n",
    "            return self.s < that.s\n",
    "        \n",
    "    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:\n",
    "        v = list()\n",
    "        for i in range(n):\n",
    "            v.append(Solution.Staff(speed[i], efficiency[i]))\n",
    "        v.sort(key=lambda x: -x.e)\n",
    "\n",
    "        q = list()\n",
    "        ans, total = 0, 0\n",
    "        for i in range(n):\n",
    "            minE, totalS = v[i].e, total + v[i].s\n",
    "            ans = max(ans, minE * totalS)\n",
    "            heapq.heappush(q, v[i])\n",
    "            total += v[i].s\n",
    "            if len(q) == k:\n",
    "                item = heapq.heappop(q)\n",
    "                total -= item.s\n",
    "        return ans % (10**9 + 7)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
